package leetcode.code1738;

import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int kthLargestValue(int[][] matrix, int k) {
		int m = matrix.length, n = matrix[0].length;
		int[][] r = new int[m][n];
		int[][] u = new int[m][n];
		PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> a - b);
		for (int i = 0; i < m; i++) {
			int xor = 0;
			for (int j = 0; j < n; j++) {
				int cur = matrix[i][j];
				xor ^= cur;
				r[i][j] = xor;
			}
		}

		for (int j = 0; j < n; j++) {
			int xor = 0;
			for (int i = 0; i < m; i++) {
				int cur = matrix[i][j];
				xor ^= cur;
				u[i][j] = xor;
			}
		}
		int[][] xors = new int[m][n];
		xors[0][0] = matrix[0][0];
		queue.add(xors[0][0]);
		for (int i = 1; i < n; i++) {
			int cur = r[0][i];
			xors[0][i] = cur;
			if (queue.size() < k) {
				queue.add(cur);
			} else if (cur > queue.peek()) {
				queue.poll();
				queue.add(cur);
			}
		}
		for (int i = 1; i < m; i++) {
			int cur = u[i][0];
			xors[i][0] = cur;
			if (queue.size() < k) {
				queue.add(cur);
			} else if (cur > queue.peek()) {
				queue.poll();
				queue.add(cur);
			}
		}
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				int me = matrix[i][j];
				int cur = me ^ r[i][j - 1] ^ u[i - 1][j] ^ xors[i - 1][j - 1];
				xors[i][j] = cur;
				if (queue.size() < k) {
					queue.add(cur);
				} else if (cur > queue.peek()) {
					queue.poll();
					queue.add(cur);
				}
			}
		}
		return queue.peek();
	}

	@Override
	public void debug4() {
		H.compare(4, this.kthLargestValue(H.str2array1("[[5,2],[1,6]]"), 3));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
